import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: dings
 * Date: 2024-07-22
 * Time: 0:36
 */

public class Test {
    public void mergeSort(int[] arr) {
        mergeSortTmp(arr,0,arr.length - 1);
    }
    public void mergeSortTmp(int[] arr,int left,int right) {
        int mid = (left + right) / 2;
        if (left >= right) {
            return;
        }

        //分解
        mergeSortTmp(arr, left, mid);
        mergeSortTmp(arr, mid + 1, right);
        //走到这里，元素已经分解，开始合并
        merge(arr,left,right,mid);
    }

    //合并
    private void merge(int[] arr, int left, int right, int mid) {
        int start1 = left;
        int end1 = mid;
        int start2 = mid + 1;
        int end2 = right;
        int len = right - left + 1;
        int[] tmp = new int[len];

        int k = 0;
        while (start1 <= end1 && start2 <= end2) {
            if (arr[start1] <= arr[start2]) {
                tmp[k++] = arr[start1++];
            }else {
                tmp[k++] = arr[start2++];
            }
        }
        while (start1 <= end1) {
            tmp[k++] = arr[start1++];
        }
        while (start2 <= end2) {
            tmp[k++] = arr[start2++];
        }
        //i+left 保证不覆盖其他区域的元素
        for (int i = 0; i < tmp.length; i++) {
            arr[i + left] = tmp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {23,12,78,4,23,11,52,100,1};
        Test test = new Test();
        test.mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
